package leetcode.weekly.week332;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

//Solution3Test
public class Solution3 {

	public int[][] substringXorQueries(String s, int[][] queries) {
		int len = queries.length;
		int[][] ans = new int[len][2];
		for (int i = 0; i < len; i++) {
			ans[i][0] = -1;
			ans[i][1] = -1;
		}
		Map<Integer, List<Integer>> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int[] q = queries[i];
			int f = q[0], se = q[1];
			int val = se ^ f;
			map.computeIfAbsent(val, key -> new ArrayList<>()).add(i);
		}
		Set<Integer> find = new HashSet<>();
		for (int i = 1; i <= 31; i++) {
			int limit = (1 << i) - 1;
			int num = 0, r = 0;
			while (r < s.length() && r < i) {
				int cur = s.charAt(r) - '0';
				num <<= 1;
				num |= cur;
				r++;
			}
			num &= limit;
			if (map.containsKey(num) && !find.contains(num)) {
				find.add(num);
				List<Integer> ids = map.get(num);
				for (int id : ids) {
					ans[id][0] = r - i;
					ans[id][1] = r - 1;
				}
			}
			while (r < s.length()) {
				int cur = s.charAt(r) - '0';
				num <<= 1;
				num |= cur;
				num &= limit;
				if (map.containsKey(num) && !find.contains(num)) {
					find.add(num);
					List<Integer> ids = map.get(num);
					for (int id : ids) {
						ans[id][0] = r - i + 1;
						ans[id][1] = r;
					}
				}
				r++;
			}
		}
		return ans;

	}
}
